#ifndef LEETCODE_CN_CPP_PROBLEMS_695_H
#define LEETCODE_CN_CPP_PROBLEMS_695_H

#include <vector>

using namespace std;

namespace problem_695
{

class Solution
{
private:
    const int dirs[5] = {0, -1, 0, 1, 0};
    int dfs(vector<vector<int>> &grid, int i, int j)
    {
        if (grid[i][j] != 1)
            return 0;
        int area = 1;
        grid[i][j] = 2;
        for (int k = 0; k < 4; ++k)
        {
            int ii = i + dirs[k];
            int jj = j + dirs[k + 1];
            if (ii >= 0 && ii < grid.size() &&
                jj >= 0 && jj < grid[i].size() &&
                grid[ii][jj] == 1)
                area += dfs(grid, ii, jj);
        }
        return area;
    }

public:
    int maxAreaOfIsland(vector<vector<int>> &grid)
    {
        int maxArea = 0;
        for (int i = 0; i < grid.size(); ++i)
            for (int j = 0; j < grid[i].size(); ++j)
                if (grid[i][j] == 1)
                    maxArea = max(dfs(grid, i, j), maxArea);
        return maxArea;
    }
};

} // namespace problem_695

#endif //LEETCODE_CN_CPP_PROBLEMS_695_H
